‎The maximum clique problem (MCP) is to determine a complete subgraph of maximum cardinality in a graph‎. ‎MCP is a fundamental problem in combinatorial optimization and is noticeable for its wide range of applications‎. ‎In this paper‎, ‎we present two branch-and-bound exact algorithms for finding a maximum clique in an undirected graph‎. ‎Many efficient exact branch and bound maximum clique algorithms use approximate coloring to compute an upper bound on the clique number but‎, ‎as a new pruning strategy‎, ‎we show that local core number is more efficient‎. ‎Moreover‎, ‎instead of neighbors set of a vertex‎, ‎our search area is restricted to a subset of the set in each subproblem which speeds up clique finding process‎. ‎This subset is based on the core of the vertices of a given graph‎. ‎We improved the MCQ and MaxCliqueDyn algorithms with respect to the new pruning strategy and search area restriction‎. ‎Experimental results demonstrate that the improved algorithms outperform the previous well-known algorithms for many instances when applied to DIMACS benchmark and random graphs‎.

In this paper, we first extend the weighted handshaking lemma, using a generalization of the concept of the degree of vertices to the values of graphs. This edge-version of the weighted handshaking lemma yields an immediate generalization of the Mantel's classical result which asks for the maximum number of edges in triangle-free graphs to the class of K4-free graphs. Then, by defining the concept of value for cliques (complete subgraphs) of higher orders, we also extend the classical result of Mantel for any graph G. We finally conclude our paper with a discussion about the possible future works.

The clique polynomial of a graph G is the ordinary generating function of the number of complete subgraphs (cliques) of G. In this paper, we introduce a new vertex-weighted version of these polynomials. We also show that these weighted clique polynomials have always a real root provided that the weights are non-negative real numbers. As an application, we obtain a no-homomorphism criteria based on the largest real root of our vertex-weighted clique polynomial.

In this paper, we give some necessary conditions for an r-partite graph such that the edge ring of the graph is Cohen-Macaulay. It is proved that if there exists a cover of an r-partite Cohen-Macaulay graph by disjoint cliques of size r, then such a cover is unique.

This paper generated the novel approach called the Clique polynomial method (CPM) using the clique polynomials raised in graph theory. Nonlinear initial value problems are converted into nonlinear algebraic equations by discretion with suitable grid points in the current approach. We solved highly nonlinear initial value problems using the Homotopy analysis method (HAM) and Clique polynomial method (CPM). Obtained results reveal that the present technique is better than HAM that is discussed through tables and simulations. Convergence analysis is reflected in terms of theorems.

A graph $G$ of order $n$ is called $k-$step Hamiltonian for $k\geq 1$ if we can label the vertices of $G$ as $v_1,v_2,\ldots,v_n$ such that $d(v_n,v_1)=d(v_i,v_{i+1})=k$ for $i=1,2,\ldots,n-1$. The (vertex) chromatic number of a graph $G$ is the minimum number of colors needed to color the vertices of $G$ so that no pair of adjacent vertices receive the same color. The clique number of $G$ is the maximum cardinality of a set of pairwise adjacent vertices in $G$. In this paper, we study the chromatic number and the clique number in $k-$step Hamiltonian graphs for $k\geq 2$. We present upper bounds for the chromatic number in $k-$step Hamiltonian graphs and give characterizations of graphs achieving the equality of the bounds. We also present an upper bound for the clique number in $k-$step Hamiltonian graphs and characterize graphs achieving equality of the bound.

In the present study we compute some bounds of multiplicative Zagreb indices and then we study these topological indices by using concept of chromatic number and clique number.